iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 28
0
自我挑戰組

學習資料結構30天系列 第 28

[Data Structure][Sort] - Merge Sort

  • 分享至 

  • xImage
  •  

前言

今天介紹一種Divide and Conquer的排序方法 - Merge Sort

Merge Sort,排序的方式就是將手上的撲克牌,分成兩堆,再對半分成兩堆,直到一張牌是一個單位的時候,再依照剛剛拆分的順序,將兩個單位(各一張牌,共兩張牌)合併回去,並且新組成的單位都會排序好數字大小,所以最後手上的牌都會排好順序。

  • Divide and Conquer 就是將複雜問題分解成很多個簡單的問題,先解決所有的簡單的問題,再把所有簡單的問題的答案合起來作為複雜問題的答案。
    • Divide : 將n個數字分成兩個(n/2)的數列
    • Conquer : 排序兩個數列
    • Combine : 合併排序過的兩個數列組成一個新的有序數列

Merge Sort

將未排序的數列,拆分成兩個幾乎等長的數列,直到不能再拆分,再合併各組的數列。
合併的時候,就是把兩個已經排序過的數列,重組成一個新的有序數列,直到全部的數組成一個數列。

  • 時間複雜度 : O(n logn)

實作:

public class Merge_Sort 
{
	public static void main (String args[])
	{
		int ex[] =  {52, 99, 31, 60, 7, 46, 53};
		
		// before sort
		PrintArray(ex); 
				
		System.out.println("--------------------");
		MergeSort(ex);
		        
		// after sort
		PrintArray(ex); 
	}

	public static void MergeSort(int arr[])
    {
		Separate(arr, arr.length);
    }
	
	public static void Separate(int arr[], int len)
    {
		// 拆分的陣列長度不會小於1
        if(len > 1)
		{
			int mid = (len + 1) / 2;
			
			int left[] =  new int [mid];
			int right[] =  new int [len - mid];
			
			for(int i = 0; i < mid; i++)
			{
				left[i] = arr[i];
			}
			
			for(int i = mid, j = 0; i < len; i++,j++)
			{
				right[j] = arr[i];
			}
			
			// Recursion
			Separate(left, left.length);
			Separate(right, right.length);
			
			//合併
			Merge(arr, left, right);
		}
		
    }
	
	public static void Merge(int arr[], int left[], int right[])
    {
		int i = 0, j = 0, k = 0; // left[]、right[]、arr[]的Index
		
		//重複比較left[],right[]兩個陣列的排頭大小,把比較小的先存進arr陣列中
		while(i < left.length && j < right.length && k < left.length + right.length)
		{
			if(left[i] <= right[j])
			{
				arr[k] = left[i];
				i++;
			}
			else
			{
				arr[k] = right[j] ;
				j++;
			}
			k++;
		}
		
		//若某一個陣列先排完,將另一個陣列剩下的數字存進arr陣列中
		while( i < left.length)
		{
			arr[k] = left[i];
			i++;
			k++;
		}
		
		while( j < right.length)
		{
			arr[k] = right[j] ;
			j++;
			k++;
		}
    }
	
	public static void PrintArray(int arr[])
	{
		for(int i = 0; i < arr.length; i++)
	    {
			System.out.print(arr[i] + " ");
	    }
		System.out.println();
	}
}

輸出結果:

52 99 31 60 7 46 53 
--------------------
7 31 46 52 53 60 99 

註: 筆者習慣數列從左到右,值會由小到大


上一篇
[Data Structure][Sort] - Insertion Sort
下一篇
[Data Structure][Sort] - Quick Sort
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言